#pragma once
#include <list>
#include <map>
#include <vector>
#include <algorithm>
#include <core/container/KeyHashMap.h>
#include "JumpListDefines.h"

#define CHECK_STATE(NODE) //if(NODE && m_flag_check){NODE->CheckState(m_comparator);}
#define CHECK_LINK(NODE,HEAD,TAIL) //if(NODE && m_flag_check){NODE->CheckLink(HEAD,TAIL);}
#define CHECK_LENGTH() //{if (m_flag_check)CheckLength();}
#define CHECK_UNIQUE() //{if (m_flag_check)CheckUnique();}
#define CHECK_NODES() // {if (m_flag_check)CheckLink();}
#define CHECK_POOL() //{if (m_flag_check)CheckPool();}

#ifndef BASSERT
#define BASSERT //
#endif

#ifndef BVIEW
#define BVIEW //
#endif


template<class Type>
class JumpObjectPool{
	std::list<Type*>		m_unused;
	int				m_capcity;		// 默认-1,表示全部缓存
	int				m_allocated;
public:
	JumpObjectPool(int capcity = -1) :m_capcity(capcity), m_allocated(0){}
	~JumpObjectPool(){
        auto it = m_unused.begin();
		for (; it != m_unused.end(); ++it)
		{
			delete *it;
		}
	}
	int GetCount()const{ return m_unused.size(); }
	int GetCapcity()const{ return m_capcity; }
	int GetAllocated()const{ return m_allocated; }
	void SetCapcity(int capcity){ m_capcity = capcity; }
	Type* Alloc(){
		Type* type = 0;
		if (!m_unused.empty())
		{
			type = m_unused.front();
			m_unused.pop_front();
		}else
			type = new Type();
		m_allocated++;
		return type;
	}
	void Free(Type* t){
		BASSERT(t);
		m_allocated--;
		if (m_capcity > 0 && (int)m_unused.size() >= m_capcity)
		{
			delete t;
		}else
			m_unused.push_back(t);
	}
};

/*
	模板参数要求:
	类Key必须是POD类型
	类Key必须由以下成员函数
		bool operator==(const Key& key)const;
		unsigned int GetHash()const
		前者用于对两个Key对象进行相等判定,如果相等,那么Insert的时候就会被替换覆盖
		后者用于计算Key的哈希值,相同哈希值的会放在相同插槽的同一个队列中

	类Comparator必须有以下成员函数
		int operator()(const Key& b1, const Key& b2)const
		int GetExpandLength(int cur, int length)
		前者用于对两个Key对象进行比较从而决定谁放在前面,谁放在后面
		后者用于如何扩展容量
*/
template<class Key, class Comparator>
class JumpList{
protected:
	//typedef BrokerKeyInfo Key;
	//typedef CBondComparatorIndirect Comparator;
	enum{
		STEP_LEVEL = 4,					// 
	};
	struct SkipNode;
	struct  Entry{							// 
		Entry*			listprev;			// 新旧关系双链表的后一个
		Entry*			listnext;			// 新旧关系双链表的前一个
		Entry*			hashprev;			// 哈西插槽的双链表的后一个
		Entry*			hashnext;			// 哈西插槽的双链表的前一个

		Key				key;				// 用于标志
		int				ver;				// 版本信息，每次写入更新，都会递增，重新加载会重置
		//int				changed;			// 值变更次数,当获取之后重置为0
		//int				sortid;				// 排序id,只用于GetKeys时检测当前视图的记录的排序是否变化
	private:
		SkipNode*		m_node;				// 
	public:
		Entry() :listprev(0), listnext(0), hashnext(0), hashprev(0), m_node(0),ver(0){}
		SkipNode* GetNode(){ return m_node; }
		void SetNode(SkipNode* n){ this->m_node = n; }
	};
#ifdef CCORE_MAC
    struct sortrData
    {
        void* arg;
        int (*compar)(const void* a1, const void* a2, void* aarg);
    };
#endif
	struct SortCheckInfo{
		Entry*	prev;
		Entry*	cur;
		int		index;
    };
	struct SkipNode{						// 跳表的加速节点
		SkipNode*		m_next;				// 同一级的下一个
		SkipNode*		m_prev;				// 同一级的上一个
		SkipNode*		m_parent;			// 上一级
		SkipNode*		m_child;				// 下一级的第一个孩子节点
		Entry*			m_entry;				// 实际内容节点
		int				m_dist;				// 与next的间距,也是子集节点的个数
		int				m_count;				// 所有子节点的Entry个数之和
		Entry* GetEntry()const{
			Entry* et = m_entry;
			SkipNode* child = m_child;
			while (child)
			{
				et=child->m_entry;
				child = child->m_child;
			}
			return et;
			// 递归实现
			//return m_child ? m_child->GetEntry() : m_entry;
		}
		Entry* GetEndEntry()const{ return m_next ? m_next->GetEntry() : 0; }
		Entry* GetLastEntry(Entry* tail = 0){
			// 分层递归，不会有栈溢出
			if (m_next)	return m_next->GetEntry()->listprev;
			if (tail)	return tail;
			if (IsLeaf())
			{
				Entry* last = GetEntry();
				for (int i = 1; i < m_dist; i++)
				{
					last = last->listnext;
				}
				return last;
			}
			return GetLastChild()->GetLastEntry(tail);
		}
		SkipNode* GetChild()const{ return m_child; }
		const SkipNode* GetFirstBrother()const{
			const SkipNode* node = this;
			const SkipNode* prev = m_prev;
			while (prev)
			{
				node = prev;
				prev = prev->m_prev;
			}
			return node;
			// 递归实现
			// return m_prev ? m_prev->GetFirstBrother() : this;
		}
		const SkipNode* GetAncestor()const{
			const SkipNode* ancestor = m_parent;
			while (ancestor && ancestor->m_parent)
			{
				if (ancestor == ancestor->m_parent)
					return 0;
				ancestor = ancestor->m_parent;
			}
			return ancestor;
		}
		SkipNode* GetLastChild()
		{
			if (m_next)	return m_next->GetChild()->m_prev;
			SkipNode* tail = m_child;
			for (int i = 1; i < m_dist; i++)
			{
				tail = tail->m_next;
			}
			BASSERT(tail->m_next==0);
			return tail;
		}
		bool IsLeaf()const{ return m_entry != 0; }
		void CheckAllEntries()
		{
			int count = 0;
			Entry* head = m_entry;
			if (head && head->GetNode() == this)
			{
				do
				{
					if (count > 0){ BASSERT(head && head->GetNode() == 0); }
					else{ BASSERT(head && head->GetNode() == this); }
					count++;
					head = head->listnext;
				} while (head && head->GetNode() == 0 && count < m_dist);
			}
		}
		int GetEntryCount()
		{
			int count = 0;
			Entry* head = m_entry;
			if (head && head->GetNode() == this)
			{
				do
				{
					count++;
					head = head->listnext;
				} while (head && head->GetNode() == 0);
			}
			return count;
		}
		int GetAllEntryCount()
		{
			if (m_child == 0)
			{
				//int ncount = GetEntryCount();
				BASSERT(m_entry && m_dist == m_count);
				//SASSERT(m_dist == ncount);
				return m_dist;
			}
			SkipNode* child = m_child;
			int count = 0;
			while (child && child->m_parent == this)
			{
				count += child->GetAllEntryCount();
				child = child->m_next;
			}
			return count;
		}
		int GetEntryIndex(Entry* entry)
		{
			if (!IsLeaf())return -1;
			Entry* head = m_entry;
			if (m_dist > 0){ BASSERT(head && head->GetNode() == this); }
			for (int i = 0; i < m_dist; i++)
			{
				if (i > 0){ BASSERT(head && head->GetNode() == 0); }
				if (head == entry)
					return i;
				head = head->listnext;
			}
			if (head){ BASSERT(head->GetNode() != 0 && head->GetNode() != this); }
			return -1;
		}
        int GetAllEntries(std::vector<Entry*>& entries)
		{
			if (!IsLeaf())return 0;
			Entry* head = m_entry;
			for (int i = 0; i < m_dist; i++)
			{
				if (i > 0){ BASSERT(head && head->GetNode() == 0); }
				else{ BASSERT(head && head->GetNode() == this); }
				entries.push_back(head);
				head = head->listnext;
			}
			if (head){ BASSERT(head->GetNode() != 0 && head->GetNode() != this); }
			return m_dist;
		}

		SkipNode* GetLeafChild(){
			// 分层递归无栈溢出
			if (IsLeaf())
				return this;
			BASSERT(m_child);
			return m_child->GetLeafChild();
		}
		SkipNode* GetEndChildNode()const{ return (m_child&&m_next) ? m_next->m_child : 0; }
		void AddCountToRoot(int plus)
		{
			SkipNode* node = this;
			while (node)
			{
				node->m_count += plus;
				node = node->m_parent;
			}
		}
		Entry* GetEntryByOffset(int offset)
		{
			// 此节点是最低级别的节点,entry不为空
			// 获取此节点管辖范围内的第offset个Entry
			BASSERT(m_entry && offset >= 0 && offset < m_dist);
			Entry* et = m_entry;
			for (int i = 0; i < offset; i++)
			{
				et = et->listnext;
			}
			return et;
		}
		SkipNode* GetNodeByOffset(int& offset)
		{
			// 分层递归无栈溢出
			// 获取在此node的管辖范围内的拥有第offset个Entry的最低节点
			if (m_child == 0)
			{
				BASSERT(m_entry != 0 && offset >= 0 && offset < m_dist);
				return this;
			}
			SkipNode* node = m_child;
			for (int i = 0; i < m_dist && node; i++)
			{
				int ncount = node->GetCount();
				if (offset < ncount)
					return node->GetNodeByOffset(offset);
				node = node->m_next;
				offset -= ncount;
			}
			return 0;
		}
		int GetCount()const{ return m_count; }
		void CheckLink(Entry* head = 0, Entry* tail = 0)
		{
			BASSERT((m_entry == 0 && m_child != 0) || (m_child == 0 && m_entry != 0));
			if (head == 0)head = GetEntry();
			if (tail == 0)tail = GetLastEntry();
			if (IsLeaf())
			{
				BASSERT(m_dist == m_count);
				Entry* first = GetEntry();
				Entry* last = GetLastEntry();
				BASSERT(first == head && last == tail);
				Entry* cur = first->listnext;
				for (int i = 1; i < m_dist; i++)
				{
					BASSERT(cur && cur->listprev == first);
					first = cur;
					cur = cur->listnext;
				}
			}else
			{
				SkipNode* child = m_child;
				for (int i = 0; i < m_dist; i++)
				{
					Entry* first = child->GetEntry();
					Entry* last = child->GetLastEntry();
					BASSERT(first == head);
					if (i == m_dist - 1){ BASSERT(last == tail); }

					child->CheckLink(first, last);
					child = child->m_next;
					head = last->listnext;
					if (head){ BASSERT(head->listprev == last); }
				}
			}
		}
		void CheckState(Comparator* comparator)
		{
			int less=0, large = 0;
			CheckState(comparator, less, large);
		}
		void CheckState(Comparator* comparator, int& less, int& large)
		{
			SkipNode* child = m_child;
			if (child)
			{
				for (int i = 0; i < m_dist; i++)
				{
					BASSERT(child->m_parent == this);
					child->CheckState(comparator, less, large);
					child = child->m_next;
				}
			}
			else
			{
				if (m_entry)
				{
					BASSERT(m_entry->GetNode() == this);
				}
				Entry* prev = m_entry;
				Entry* cur = m_entry ? m_entry->listnext : 0;
				for (int i = 1; i < m_dist; i++)
				{
					int cmp = (*comparator)(prev->key, cur->key);
					if (cmp <= 0)less++;
					if (cmp >= 0)large++;
					prev = cur;
					cur = cur->listnext;
				}
			}
		}
        void GetChildLengths(std::vector<int>& lengths, int level = 0)
		{
			if (level == 0)
			{
				lengths.push_back(m_dist);
			}
			else
			{
				SkipNode* child = m_child;
				for (int i = 0; child && i < m_dist; i++)
				{
					if (level == 0)
						lengths.push_back(m_dist);
					else
						child->GetChildLengths(lengths, level - 1);
					child = child->m_next;
				}
			}

		}
	};
    typedef std::vector<Entry*> EntryPtrVec;
public:
	typedef JumpObjectPool<Entry> EntryPool;
	typedef JumpObjectPool<SkipNode> SkipNodePool;
protected:
	template<int N, class Allocator>
	class SkipNodeBuilder{
        typedef std::vector<SkipNode*> SkipNodePtrVec;
		int					m_step_count;
		SkipNodePtrVec		m_heads[N];
		EntryPtrVec			m_entries;			// 只在BeginPush,EndPush中使用
	public:
		SkipNodeBuilder(int stepCount) :m_step_count(stepCount){
		}
		EntryPtrVec& GetEntries(){ return m_entries; }
		void Start(int count)
		{
			m_entries.clear();
			m_entries.reserve(count);
			for (int i = 0; i < N; i++)
			{
				m_heads[i].clear();
				m_heads[i].reserve(m_step_count);
			}
		}
		void Add(Entry* entry){ m_entries.push_back(entry); }
		SkipNode* Build(Allocator* allocator)
		{
			/*
			N:是节点层级,通常3层也就足够了
			m_step_count:是每层节点能管理的底层节点的个数,初始创建时采用固定值
			m_heads[0] 是叶子节点层,直接指向Entry*
			m_heads[N-1]是顶级节点层,m_root==m_heads[N-1][0]
			steps[N]	是每层节点所能管理的Entry*的最大个数,也是该层节点

			关系如图:
			(head)																							(tail)
			Entry---------->Entry---------->Entry---------->Entry---------->Entry---------->Entry---------->Entry-->0
			^                               ^                               ^                               ^
			0:	SkipNode----------------------->SkipNode----------------------->SkipNode----------------------->SkipNode
			^                                                               ^
			1:	SkipNode------------------------------------------------------->SkipNode->0
			^
			2:	SkipNode->0
			(root)
			*/
			int steps[N] = { 0 };
			for (int i = 0; i < N; i++)
				steps[i] = (i == 0) ? m_step_count : (steps[i - 1] * m_step_count);

			int nlength = m_entries.size();
			if (nlength <= 0)
				return 0;
			for (int k = N - 1; k >= 0; k--)
			{
				int step = steps[k];
				int step2 = k >= 1 ? steps[k - 1] : 1;
				SkipNodePtrVec& heads = m_heads[k];
				for (int i = 0; i < nlength; i += step)
				{
					SkipNode* node = allocator->NewNode();
					node->m_entry = k == 0 ? m_entries[i] : 0;
					if (node->m_entry)
						node->m_entry->SetNode(node);
					//node->m_dist = ((nlength-i)/step2>m_step_count)?m_step_count:((nlength-i)/step2);
					node->m_count = (nlength - i > step) ? step : (nlength - i);
					node->m_dist = node->m_count / step2;
					if (step2*node->m_dist < node->m_count)
						node->m_dist++;

					SkipNode* prev = 0;
					if (heads.size()>0)
						prev = heads[heads.size() - 1];
					if (prev)	prev->m_next = node;
					node->m_prev = prev;

					SkipNode* parent = 0;
					if (k + 1 < N && m_heads[k + 1].size() > 0)
					{
						int pindex = i / steps[k + 1];
						BASSERT(pindex >= 0 && pindex < (int)m_heads[k + 1].size());
						parent = m_heads[k + 1].at(pindex);
					}
					if (k < N - 1){ BASSERT(parent != 0); }

					node->m_parent = parent;
					if (parent && parent->m_child == 0)
					{
						//parent->m_dist=1;
						parent->m_child = node;
						BASSERT(parent->m_dist > 0);
					}

					heads.push_back(node);
				}
			}
			SkipNode* root = m_heads[N - 1][0];
			//root->CheckState(m_comparator);
			return root;
		}
    };
	typedef SkipNodeBuilder<STEP_LEVEL, JumpList> NodeBuilder;
	qb::base::KeyHashMap<Entry, Key>*	m_hashmap;			// 根据Key来直接找到对象,快速定位
	SkipNode*				m_root;				// 根加速节点,参考了SkipList
	Entry*					m_head;				// 真实数据双链表头
	Entry*					m_tail;				// 真实数据双链表尾
	int						m_count;				// m_head和m_tail组成的双链表长度
	int						m_step_count;		//
	int						m_step_max;			//
	int						m_bsearch_dist;		// 经过测试,取值4,6,8最佳,默认4
	int						m_node_count;		// 
	Comparator*				m_comparator;		// 比较器
	EntryPool				m_entry_pool;		// Entry缓存池,缓存全部
	SkipNodePool				m_node_pool;			// SkipNode缓存池,最多缓存STEP_COUNT*STEP_LEVEL
	double					m_expand_ratio;		// 哈希表扩容比例,默认为3.0
	NodeBuilder*				m_node_builder;		// SkipNode加速树构建工具,可以进一步多个JumpList分享使用

	bool						m_flag_erasehash;	// 默认false,false比true速度提升约21%
	bool						m_flag_stepsearch;	// 默认打开,使用步进法缩小范围,性能更好
	bool						m_flag_sharepool;	// 
	bool						m_flag_check;		// 是否调用CheckNode,默认false,打开会稍微影响性能,内部测试打开,对外关闭
	bool						m_flag_check_all;	// 始终检测全部队列,默认false,打开会强烈影响性能
	bool						m_flag_failcheck;	// 自动检测其中的顺序有问题的地方,并纠正,默认打开
	bool						m_flag_screencheck;

	int						m_find_exist_sum;	// FindExist中累计的查找步数
	int						m_find_exist_count;	// FindExist中查找次数
	int						m_last_find_step;	// 上次的查找步数
	double					m_check_time;
	std::list<Key>			m_failed_keys;
	std::vector<Key>				m_screen_records;
	int						m_brokerid;
public:
	class KeyIterator{
		int				m_sortid;
		Entry*			m_current;
		Key				m_blank;
	public:
		KeyIterator() :m_sortid(-1), m_current(0){}
		KeyIterator(int sortid, Entry* entry) :m_sortid(sortid), m_current(entry){}
		KeyIterator(const KeyIterator& ki) :m_sortid(ki.m_sortid), m_current(ki.m_current){}
		KeyIterator& operator=(const KeyIterator& ki){
			m_sortid = ki.m_sortid; m_current = ki.m_current; m_blank = ki.m_blank;
			return *this;
		}
		const Key& operator*()const{ return m_current ? m_current->key : m_blank; }
		KeyIterator& operator++(){
			m_current = m_current ? m_current->listnext : NULL;
			m_sortid++;
			return *this;
		}
		bool operator!=(const KeyIterator& ki){ return m_current != ki.m_current; }
		bool operator==(const KeyIterator& ki){ return m_current == ki.m_current; }
	};

public:
	JumpList(Comparator* comparator = 0, int stepCount = 40, int hashInitSize = 2560) :
		m_comparator(comparator),
		m_root(0), m_head(0), m_tail(0), m_hashmap(0),
		/*m_node_pool(stepCount*STEP_LEVEL),*/ m_bsearch_dist(4),
		m_step_count(stepCount), m_step_max((int)(stepCount*2.28)), m_node_count(0),
		m_node_builder(0), m_count(0), m_expand_ratio(3.0),
		m_flag_erasehash(true), m_flag_stepsearch(true),
		m_flag_sharepool(false), m_last_find_step(0),m_flag_failcheck(true),
		m_flag_check(false), m_flag_check_all(false),
		m_check_time(0.0),
		m_flag_screencheck(true),m_brokerid(-1)
	{
		//#ifdef USE_SHARE_POOL
		//		if (ss::base::CPathUtil::IsFileExist("config/fflags/flag_share_pool"))
		//		{
		//			m_flag_sharepool = true;
		//			DVIEW("config/fflags/flag_share_pool is true,use m_flag_sharepool");
		//		}
		//#endif
		m_find_exist_sum = m_find_exist_count = 0;
		m_hashmap = new qb::base::KeyHashMap<Entry, Key>();
		m_hashmap->Build(hashInitSize);
	}
	virtual ~JumpList()
	{
		Clear();
		if (m_hashmap)		delete m_hashmap;
		if (m_node_builder)	delete m_node_builder;
	}
	KeyIterator GetBegin(){ return KeyIterator(0, m_head); }
	KeyIterator GetEnd(){ return KeyIterator(); }

	void SetBrokerId(int brokerid){m_brokerid=brokerid;}
	void SetComparator(Comparator* comparator){ m_comparator = comparator; }
	void SetStepMax(int stepMax){ m_step_max = stepMax; }
	void SetStepSearch(bool stepSearch){ m_flag_stepsearch = stepSearch; }
	void SetCheckFlag(bool check){ m_flag_check = check; }
	void SetCheckAllFlag(bool checkAll){ m_flag_check_all = checkAll; }
	void SetBSearchDist(int dist)
	{
		dist = dist < 3 ? 3 : dist;
		dist = dist > 128 ? 128 : dist;
		m_bsearch_dist = dist;
	}
	void Clear()
	{
		Entry* head = m_head;
		while (head)
		{
			Entry* temp = head;
			head = head->listnext;
			GetEntryPool().Free(temp);
		}
		m_head = m_tail = 0;
		m_count = 0;

		SkipNode* node = m_root;
		SkipNode* heads[STEP_LEVEL] = { 0 };
		for (int i = 0; node && i < STEP_LEVEL; i++)
		{
			heads[i] = node;
			node = node->GetChild();
		}
		for (int i = 0; i < STEP_LEVEL; i++)
		{
			node = heads[i];
			while (node)
			{
				SkipNode* temp = node;
				node = node->m_next;
				GetSkipNodePool().Free(temp);
			}
		}
		m_node_count = 0;
		m_root = 0;
		m_hashmap->Clear();
		m_head = m_tail = 0;
	}
	void BeginPush(int count)
	{
		Clear();
		if (m_node_builder == 0)
			m_node_builder = new NodeBuilder(m_step_count);
		m_node_builder->Start(count);
	}

	void Push(const Key& key)
	{
		Entry* entry = NewEntry(key);
		InsertAt(NULL, entry);
		m_node_builder->Add(entry);
	}
	void EndPush(bool resort)
	{
		EntryPtrVec& m_entries = m_node_builder->GetEntries();
		if (resort)
		{
			if (m_entries.size() > 1)
#ifdef _MSC_VER
				qsort_s(&m_entries.at(0), m_entries.size(), sizeof(Entry*), Compare, &m_comparator);
#elif defined (CCORE_MAC)
            {
                sortrData cmp;
                cmp.arg = &m_comparator;
                cmp.compar = CompareR;
                qsort_r(&m_entries.at(0), m_entries.size(), sizeof(Entry*), &cmp, &sort_r_arg_swap2);
            }
#else
				qsort_r(&m_entries.at(0), m_entries.size(), sizeof(Entry*), CompareR, &m_comparator);
#endif
		}
		if (m_entries.size() > 0)
		{
			for (int i = 0; i < (int)m_entries.size(); i++)
			{
				Entry* et = m_entries[i];
				m_hashmap->Insert(et, et->key.GetHash());
			}
			m_root = m_node_builder->Build(this);
			CheckLink();
			BASSERT(m_head && m_head->GetNode() != 0);
		}

		CHECK_UNIQUE();
		CHECK_POOL();
	}
#ifdef CCORE_MAC
    static int sort_r_arg_swap2(void* s, const void* aa, const void* bb)
    {
        struct sortrData* ss = (struct sortrData*)s;
        return (ss->compar)(aa, bb, ss->arg);
    }
#endif
	static int Compare(void* context, const void* p1, const void* p2)
	{
		Comparator* comparator = (Comparator*)context;
		const Entry* e1 = *(const Entry**)p1;
		const Entry* e2 = *(const Entry**)p2;
		return comparator->operator()(e1->key, e2->key);
	}

	static int CompareR(const void* p1, const void* p2, void* context)
	{
		Comparator* comparator = (Comparator*)context;
		const Entry* e1 = *(const Entry**)p1;
		const Entry* e2 = *(const Entry**)p2;
		return comparator->operator()(e1->key, e2->key);
	}

	bool IsExist(const Key& key)
	{
		Entry* et=m_hashmap->Find(key,key.GetHash());
		return et!=0?true:false;
	}
	int  GetVersion(const Key& key)
	{
		Entry* et=m_hashmap->Find(key,key.GetHash());
		return et?et->ver:-1;
	}
	void Insert(const Key& key, kJumpInsertWhere where = kJumpInsertWhereFind)
	{
		/*
		应用场景:key所代表的记录更新了,期望在此容器中调节此记录的顺序
		设计要求:0.1ms即10000/s的速度更新
		算法复杂度分析:
		1.FindInsert:分两个步骤
		第一步,从根节点m_root,找到待插入的entry位置的叶子节点
		第二部,从叶子节点,使用顺序/二分法找到待插入的entry位置
		2.InsertAt:Entry双链表插入,更新指针
		3.逐层更新计数
		4.节点裂变维持平衡

		总操作数为:
		+节点树层级*每层长度*比较
		+叶子节点长度*比较
		+节点树层级*计数更新
		+节点树层级*节点更新(此操作每间隔STEP_MAX执行一次)
		*/
		//1.找到要插入的位置和加速节点(相等值末尾)
		//2.插入到双链表中
		//3.更新加速节点树

		/*
		后续改进:
		FindExist 中,找到ParentNode所需要的遍历长度,如何降低此长度
		如果将parent写到每个Entry中,是否可行?测试下性能对比
		FindInsertEntry/FindInsertPosition中,步进次数是比较次数的大概322/29=11倍,时间是1.151/0.102=11倍
		因此,降低步进次数与降低比较次数同样重要
		可测试按照一定间距跳跃的算法来看看性能对比如何
		纯二分法,总的步进次数可能会很高
		ObjectPool中,Alloc,Free都话费了时间,是否可以在进一步降低?
		1.Insert/Erase 避免从hashmap中反复删除和插入
		2.Insert中,是要调用比较器来比较的
		鉴于此处代码比较器总是将要插入的值作为第一个参数
		因此,在Insert开头,可以调用接口,通知比较器,预先准备好第一个参数对应的记录的排序字段值
		避免后续比较的时候反复读取
		将几个关键函数由递归改为非递归实现如GetEntry
		使用更快更均匀的哈希函数
		测试哈希的平均分布情况,看哈希的最大list长度是多少
		测试SkipNode在多次插入后的分布情况,是不是偏离最开始的STEP_COUNT
		禁用宏断言,对比下前后性能改进
		*/
		//CHECK_NODES();
		m_check_time = 0.0;
		unsigned int hash = key.GetHash();
		Entry* exist = EraseImp(key, hash, false);

		SkipNode* last = 0;
		Entry* entry = where == kJumpInsertWhereHead ? m_head : (where == kJumpInsertWhereTail ? 0 : FindInsert(key, last));
		if (m_flag_erasehash){ BASSERT(exist == 0); }
		Entry* newentry = exist ? exist : NewEntry(key);
		InsertAt(entry, newentry);


		if (m_flag_erasehash || exist == 0)
		{
			//BASSERT(newentry != 0);
			m_hashmap->Insert(newentry, hash);
		}

		if (last == 0)
		{
			BASSERT(m_root == 0);
			SkipNodeBuilder<STEP_LEVEL, JumpList> nodesBuilder(m_step_count);
			nodesBuilder.Start(1);
			nodesBuilder.Add(newentry);
			m_root = nodesBuilder.Build(this);
			last = m_root->GetLeafChild();
			BASSERT(last);
			SetNode(newentry, last);
		}
		else
		{
			BASSERT(last->IsLeaf());
			if (entry == last->m_entry)
			{
				BASSERT(newentry->listnext == entry && entry->GetNode() == last);
				SetNode(entry, 0);
				SetNode(newentry, last);
				last->m_entry = newentry;
			}
			BASSERT(m_head->GetNode());
			BASSERT(last->GetEntry() && last->GetEntry()->GetNode() == last);
			last->m_dist++;
			last->AddCountToRoot(1);
		}
		
		//last->CheckAllEntries();
		BASSERT(last->IsLeaf());
		/*int realcount = last->GetEntryCount();
		if(realcount!=last->m_dist)
		{
		realcount=last->GetEntryCount();
		}*/
		SkipNode* parent = SplitFullNode(last);
		CheckNode("insert>split",parent);
		if (m_count % 32 == 0)
			ExpandHashList();
	}
	bool Erase(const Key& key, unsigned int hash = 0)
	{
		m_check_time = 0.0;
		JumpList::Entry* et = EraseImp(key, 0, true);
		return et != 0;
	}
	bool Find(Key& key,unsigned int hash = 0)
	{
		SkipNode* leaf = 0;
		hash = (hash == 0) ? key.GetHash() : hash;
		Entry* entry = FindExist(key, leaf, hash);
		if (!entry)
			return false;
		key = entry->key;
		return true;
	}
	int GetCount()const{ return m_count; }

    void GetAllKeys(std::vector<Key>& allKeys)const
	{
		Entry* head = m_head;
		allKeys.clear();
		while (head)
		{
			allKeys.push_back(head->key);
			head = head->listnext;
		}
	}
    int GetKeys(int index, int count, std::vector<Key>& keys)
	{
		keys.clear();
		for (int i = 0; i < count;i++){keys.push_back(Key());}
		int num = GetKeys(index, count, &keys.at(0));
		while (keys.size()>num)
		{
			keys.erase(keys.begin() + num);
		}
		return num;
	}
	int GetKeys( int index,int count,Key* keys )
	{
		/*
		应用场景:UI界面要求获取从排序index开始的若干记录
		设计要求:非常快,1ms
		算法复杂度分析:
		GetNodeByOffset 是通过计算节点树的总共个数,从而判断顺序
		而且总的节点树层级为0-10,非常少,

		GetEntryByOffset则是在最底层节点的entry 列表中定位
		总的操作次数为:
		+节点树层级数*GetCount()(<=10)
		+最底层节点树的长度*移动指针(<=256,最大不超过256)
		*/
		int added = 0;
		int try_count = 2; 
		int expect_count = m_count - index;
		expect_count = expect_count <= 0 ? 0 : expect_count;
		expect_count = expect_count >= count ? count : expect_count;
		count = (index + count) >= m_count ? (m_count - index ): count;
		count = count <= 0 ? 0 : count;
		SkipNode* node = m_root;
		while (try_count > 0)
		{
			added=GetKeysImpl(index,count,keys,node);
			if(added>=expect_count)
				break;
			try_count--;
		}
		if(m_flag_screencheck && added>0)
		{
			int nsize = m_screen_records.size();
			bool sortok = true;
			for(int i=1;sortok && i<nsize;i++)
			{
				Key& prev = m_screen_records[i - 1];
				Key& cur = m_screen_records[i];
				
				int cmp = (*m_comparator)(prev, cur);
				if(cmp>0)
					sortok=false;
			}
			if(!sortok)
			{
				class EntryComp{
					Comparator*				m_comparator;
				public:
					EntryComp(Comparator* cmp):m_comparator(cmp){}
					EntryComp(const EntryComp& ec){ m_comparator = ec.m_comparator; }
					bool operator()(const Key& e1, const Key& e2)const
					{
						return (*m_comparator)(e1,e2)<0;
					}
				};
				std::sort(m_screen_records.begin(),m_screen_records.end(),EntryComp(m_comparator));
				int i = 0;
				for(;i<count && i<(int)m_screen_records.size();i++)
					keys[i]=m_screen_records[i];
				m_screen_records.clear();
				added=i;
			}
		}
		if (m_flag_check && node)
		{
			if(m_flag_failcheck)
				m_failed_keys.clear();

			SkipNode* checknode = node->m_parent ? node->m_parent : node;
			CheckNode("getkeys",checknode,0,m_flag_failcheck);
			if(m_flag_failcheck && !m_failed_keys.empty())
			{
				int ncount = m_failed_keys.size();
                for (auto it=m_failed_keys.begin();it!=m_failed_keys.end();++it)
				{
					SkipNode* leaf=0;
					BASSERT(this->FindExist(*it,leaf,0));
					Insert(*it);
					BASSERT(this->FindExist(*it,leaf,0));
				}
				added=GetKeysImpl(index,count,keys,node);
				if (m_flag_screencheck)
				{
					m_screen_records.clear();
				}

				m_failed_keys.clear();
				CheckNode("getkeys>recheck",checknode,0,m_flag_failcheck);
				if(m_failed_keys.size()>0)
				{
					int a = 0;
					//BVIEW("m_failed_keys before:%d  after:%d",ncount,m_failed_keys.size());
				}
				m_failed_keys.clear();
			}
		}
		return added;
	}
	int GetKeysImpl(int index,int count,Key* keys,SkipNode*& node)
	{
		if (m_flag_screencheck)
		{
			m_screen_records.clear();
			m_screen_records.reserve(count);
		}
		int added = 0;
		int offset = index;
		node = m_root;
		while (node)
		{
			if (offset < node->GetCount())
				break;
			offset -= node->GetCount();
			node = node->m_next;
		}
		node = node ? node->GetNodeByOffset(offset) : 0;
		if (node)
		{
			int less = 0,large=0;
			Entry* prev = 0;
			
			Entry* entry = node->GetEntryByOffset(offset);
			for (int i = 0; i < count && entry; i++)
			{
				//const char* name = AfxGetBondContainer().ElementAt(entry->key.m_nIndex).GetBondShortName();
				//BVIEW("\n%d\t%d\t%d\t%s", i, entry->key.m_nIndex, entry->key.m_nBrokerId, name);
				if(m_flag_screencheck)
					m_screen_records.push_back(entry->key);
				keys[added++]=entry->key;
				prev = entry;
				entry = entry->listnext;
			}
		}
		return added;
	}
	void CheckSort()
	{
		if (m_head == 0 || m_head->listnext == 0)
			return;
		int less = 0, large = 0;
		Entry* prev = m_head;
		Entry* cur = m_head->listnext;
		for (int i = 1;; i++)
		{
			int cmp = (*m_comparator)(prev->key, cur->key);
			if (cmp <= 0)less++;
			if (cmp >= 0)large++;
			if (cur == m_tail)
				break;
			prev = cur;
			cur = cur->listnext;
		}
		if (less + 1 < m_count && large + 1 < m_count){ BVIEW("sort check failed,less:%d large:%d", less, large); }
        else{ BVIEW("sort check success,%s", less > 0 ? "asccend" : "desccend"); }
	}
	void CheckLink()
	{
		if (m_root)
		{
			BASSERT(m_head != 0 && m_tail != 0);
			BASSERT(m_root->GetEntry() == m_head);
			BASSERT(m_head->GetNode() == m_root->GetLeafChild());
			BASSERT(m_root->m_next != m_root && m_root->m_prev != m_root && m_root->m_child != m_root);
		}
		SkipNode* leaf = m_root ? m_root->GetLeafChild() : 0;
		while (leaf)
		{
			BASSERT(leaf->m_next != leaf && leaf->m_prev != leaf && leaf->m_child != leaf);
			if (leaf->m_entry->GetNode() != leaf)
				SetNode(leaf->m_entry, leaf);
			leaf = leaf->m_next;
		}
	}
	void CheckState()
	{
		int less = 0, large = 0;
		if (m_root)
		{
			m_root->CheckState(m_comparator, less, large);
			if (less + 1 < m_count && large + 1 < m_count){ 
				BVIEW("sort check failed,less:%d large:%d,count:%d", less, large,m_count); 
			}
            else{ BVIEW("sort check success,%s", less > 0 ? "asccend" : "desccend"); }
		}
		if (m_root){ m_root->CheckLink(0, 0); }
	}
	void CheckLength()
	{
		Entry* et = m_head;
		int length = 0;
		while (et)
		{
			et = et->listnext;
			length++;
		}
		BASSERT(length == m_count);
	}
	void CheckUnique()
	{
		int equal_count = 0;
		std::map<Key, int> keys;
		Entry* entry = m_head;

		int pos = 0;
		while (entry)
		{
            auto it = keys.find(entry->key);
			if (it == keys.end())
				keys.insert(std::map<Key, int>::value_type(entry->key, 1));
			else
			{
				equal_count++;
				it->second = it->second + 1;
			}
			pos++;
			entry = entry->listnext;
		}
		SkipNode* leaf = 0;
        for (auto it = keys.begin(); it != keys.end(); ++it)
		{
			if (it->second <= 1)	continue;
			entry = FindExist(it->first, leaf, 0);
			const Key& key = it->first;
			//BVIEW("index:%d  brokerid:%d  count:%d", key.m_nIndex, key.m_nBrokerId, it->second);
		}
	}
	void CheckPool()
	{
#ifdef WIN32
		static DWORD last = GetTickCount();
		if (last + 5000 < GetTickCount())
		{
			last = GetTickCount();
			//DVIEW("this_entry_pool:%d,%d,%d,this_node_pool:%d,%d,%d,share_entry_pool:%d,%d,%d,share_node_pool:%d,%d,%d",
			//	m_entry_pool.GetCount(), m_entry_pool.GetCapcity(), m_entry_pool.GetAllocated(),
			//	m_node_pool.GetCount(), m_node_pool.GetCapcity(), m_node_pool.GetAllocated(),
			//	g_share_entry_pool.GetCount(), g_share_entry_pool.GetCapcity(), g_share_entry_pool.GetAllocated(),
			//	g_share_node_pool.GetCount(), g_share_node_pool.GetCapcity(), g_share_node_pool.GetAllocated()
			//	);
		}
#endif
	}
	void CheckNode(const char* context,SkipNode* node,int level=0,bool failCheck=false)
	{
		m_check_time = 0.0;
		if (!m_flag_check)return;
		if (level==0 && m_flag_check_all){ node = m_root; }
        std::vector<SortCheckInfo> failedList;
		if (node)
		{
			// node一定要在root树中
			BASSERT(node == m_root || 
				node->GetFirstBrother() == m_root ||
				node->GetAncestor()->GetFirstBrother() == m_root);
			
			// node的相关指针一定不能指向自己
			BASSERT(node->m_parent != node && node->m_child != node && node->m_prev != node && node->m_next != node);

			// 0<m_dist<=m_count,为0的一定要被删除清理掉
			BASSERT(node->m_dist <= node->m_count);
			BASSERT(node->m_dist > 0);
			if (node->IsLeaf())
			{
				BASSERT(node->m_dist == node->m_count);
				BASSERT(node->GetEntryCount() == node->m_count);
				BASSERT(node->m_entry && node->m_entry->GetNode() == node);
				BASSERT(node->m_child == 0);

				Entry* et = node->GetEntry();
				Entry* prev = et->listprev;
				Entry* end = node->m_next ? node->m_next->GetEntry() : 0;
				if (prev == 0){ BASSERT(et == m_head); }
				for (int i = 0; i < node->m_dist; i++)
				{
					// 检测Node与Entry的指针是否正确,Node的m_entry指向第一个entry,但只有Node的第一个Entry才指向Node
					SkipNode* target = i == 0 ? node : 0;
					BASSERT(et && et->GetNode() == target);

					// 检测
					BASSERT(et->listprev == prev);
					prev = et;
					et = et->listnext;
				}

				// 末尾检测,验证m_dist正确性
				BASSERT(et == end);
				if (end == 0){ BASSERT(prev == m_tail); }

			}
			else
			{
				// node的所有entry个数一定要等于m_count
				BASSERT(node->m_count == node->GetAllEntryCount());

				// 非叶子节点的m_child一定不能为0
				BASSERT(node->GetChild() != 0);


				SkipNode* child = node->GetChild();
				SkipNode* prev = child->m_prev;
				SkipNode* end = node->m_next ? node->m_next->GetChild() : 0;

				
				for (int i = 0; i < node->m_dist; i++)
				{
					// 父子节点的关系检测
					BASSERT(child && child != end);
					BASSERT(child->m_parent == node);
					BASSERT(child->m_prev == prev);
					CheckNode("checknode",child, level + 1);
					prev = child;
					child = child->m_next;
				}

				// 末尾检测,验证m_dist正确性
				BASSERT(child == end);
			}
		}
		if (level == 0)
		{
			BASSERT(m_count == m_hashmap->GetCount());
			if (node)
			{
				Entry* prev = node->GetEntry();
				Entry* cur = prev->listnext;
				int ncount = node->GetAllEntryCount();
				int less = 0, large = 0;
				for (int i = 1; i < ncount; i++)
				{
					BASSERT(prev!=cur);
					int cmp = (*m_comparator)(prev->key, cur->key);
					if (cmp <= 0)less++;
					if (cmp > 0 && failCheck){
						SkipNode* leaf=0;
						BASSERT(this->FindExist(prev->key,leaf,0));
						m_failed_keys.push_back(prev->key);
					}
					prev = cur;
					cur = cur->listnext;
				}
				if (failCheck && !m_failed_keys.empty())
				{
					//char buf[256]={0};int len=0;
					//char* ptr = buf;int left=len-1;char* pend = buf+left;
					//for(std::std::list<Key>::iterator it=m_failed_keys.begin();ptr<pend && it!=m_failed_keys.end();++it)
					//{
					//	Key& key = *it;
					//	int num=_snprintf_s(ptr,left,_TRUNCATE,"%d-%d-%d",0,key.m_nIndex,key.m_nBrokerId);
					//	ptr+=num;left-=num;
					//}
					//BVIEW("sort check failed,brokerid:%d context:%s less:%d large:%d  ncount:%d  total:%d keys:%s",
					//	m_brokerid,context,less, m_failed_keys.size(),ncount,m_count,buf);
				}
			}
			CheckLink();
		}
	}
	double GetCheckTime()const{ return m_check_time; }
	int GetBytes()const
	{
		int bytes = m_hashmap->GetBytes();
		bytes += m_node_count*sizeof(SkipNode) + m_count*sizeof(Entry);
		bytes += (m_node_pool.GetCount() + m_entry_pool.GetCount())*sizeof(void*);
		bytes += sizeof(*this);
		return bytes;
	}
    void GetChildLengths(std::vector<int>& lengths, int level = 0)
	{
		if (m_root)
			m_root->GetChildLengths(lengths, level);
	}
	double GetFindExistStep()
	{
		return m_find_exist_count == 0 ? 0 : (m_find_exist_sum*1.0 / m_find_exist_count);
	}
protected:
	Entry* FindExist(const Key& key, SkipNode*& leaf, unsigned int hash)
	{
		Entry* entry = m_hashmap->Find(key, hash == 0 ? key.GetHash() : hash);
		if (!entry)
			return 0;
		leaf = 0;
		int step = 0;
		Entry* et = entry;
		while (et)		// 最多遍历一定长度,找到加速节点
		{
			if (et->GetNode())
			{
				leaf = et->GetNode();
				break;
			}
			et = et->listprev;
			step++;
		}
		m_last_find_step = step;
		m_find_exist_sum += step;
		m_find_exist_count++;
		return entry;
	}
	Entry* FindInsert(const Key& key, SkipNode*& leaf)
	{
		if (m_root == 0)
		{
			leaf = 0;
			return 0;
		}
		SkipNode* root = m_root;
		SkipNode* next = m_root->m_next;
		while (next)
		{
			Entry* et = next->GetEntry();
			BASSERT(et);
			if ((*m_comparator)(key, et->key) > 0)
			{
				root = next;
				next = root->m_next;
			}else
				break;
		}
		BASSERT(root && m_tail);
		int cmp = (*m_comparator)(key, m_tail->key);
		if(cmp>=0)
		{
			int step = 0;
			for (Entry* et=m_tail;et;et=et->listprev,step++)
			{
				if(et->GetNode())
				{
					leaf=et->GetNode();
					break;
				}
			}
			BASSERT(leaf);
			BASSERT(leaf->IsLeaf() && leaf->GetCount()>step);
			BASSERT(leaf == m_root || 
				leaf->GetFirstBrother() == m_root ||
				leaf->GetAncestor()->GetFirstBrother() == m_root);
			return 0;
		}

		Entry* entry = FindInsertPosition(key, root, leaf);
		CheckInsertPos(entry,key);
		return entry;
	}
	void CheckInsertPos(Entry* entry,const Key& key)
	{
		if (!m_flag_check)return;
		if (entry)
		{
			BASSERT(entry);
			int cmp = (*m_comparator)(key, entry->key);
			BASSERT(cmp < 0);// 不能相等,否则key将还要插到entry的后面而不是entry所在位置
			Entry* prev = entry->listprev;
			Entry* next = entry->listnext;
			if(prev)
			{
				cmp = (*m_comparator)(prev->key, key);
				BASSERT(cmp<=0);
			}
			else{ BASSERT(entry == m_head); }
			if(next)
			{
				cmp = (*m_comparator)(entry->key, next->key);
				BASSERT(cmp<=0);
			}
			else{ BASSERT(entry == m_tail); }
		}
		else if (m_tail)
		{
			int cmp = (*m_comparator)(key, m_tail->key);
			BASSERT(cmp >= 0);
		}
	}
	Entry* FindInsertEntry(const Key& key, SkipNode* root, SkipNode*& parent)
	{
		class EntryPos{
		public:
			Entry*			entry;
			int				index;
			EntryPos(Entry* et, int i) :entry(et), index(i){}
			EntryPos(const EntryPos& ip) :entry(ip.entry), index(ip.index){}
			inline void ToRight(int step){
				index += step;
				for (int i = 0; i < step; i++){ entry = entry->listnext; }
			}
		};
		// m_tail只是用于快速找到末尾表项Entry
		// 限定root为叶子节点，对于叶子节点,m_dist==m_count
		BASSERT(root && root->IsLeaf() && root->m_dist==root->m_count);

		EntryPos left(root->GetEntry(), 0);
		EntryPos mid = left;
		EntryPos right(root->GetLastEntry(m_tail), root->m_dist - 1);
		if (!m_flag_stepsearch)
		{
			// 使用标准的二分法来缩小范围
			while (right.index - left.index > m_bsearch_dist)
			{
				mid = left;
				mid.ToRight((right.index - left.index) >> 1);
				if ((*m_comparator)(key, mid.entry->key) >= 0)
					left = mid;
				else
					right = mid;
			}
		}
		else if (right.index - left.index > m_bsearch_dist)
		{
			// 使用多步的二分法来缩小范围
			// 有微弱的优势3%和较小的时间波动
			EntryPos tempmid = left, temp = left;
			int step = 0;
			while (right.index - left.index > m_bsearch_dist)
			{
				mid = left;
				step = (right.index - left.index);
				step = (m_bsearch_dist == 4) ? (step >> 2) : (step / m_bsearch_dist);
				for (int i = 0; i < m_bsearch_dist - 1; i++)
				{
					mid = left;
					mid.ToRight(step);
					if ((*m_comparator)(key, mid.entry->key) >= 0)
						left = mid;
					else
					{
						right = mid;
						break;
					}
				}
			}
		}

		// 如果新插入key与现有的一系列key比较相等，那么插入其末尾
		mid = left;
		for (int i = left.index; i <= right.index; i++, mid.ToRight(1))
		{
			if ((*m_comparator)(key, mid.entry->key) < 0)
			{
				parent = root;
				return mid.entry;
			}
		}
		// 应该插入到此叶子节点root的下一个节点
		if(root->m_next)
		{
			parent = root->m_next;
			return parent->GetEntry();
		}

		// 当前叶子节点是最末尾的叶子节点
		// 返回0表示插入位置为末尾，替换m_tail
		if(root->m_next)
		{
			parent = root->m_next;
			return parent->GetEntry();
		}
		parent = root;
		return 0;
	}

	/*
		在节点root下面找出key应该插入的位置，并返回应该后移的Entry
		插入后，顺序应该是 m_head,...key,返回Entry*,...,m_tail
		                                      ^  
		key为待插入的Entry的key，该key肯定已经不在队列中
	*/
	Entry* FindInsertPosition(const Key& key, SkipNode* root, SkipNode*& parent)
	{
		
		class NodePos{
		public:
			SkipNode*		node;
			int				index;
			NodePos(SkipNode* sn, int i) :node(sn), index(i){}
			NodePos(const NodePos& ip) :node(ip.node), index(ip.index){}
			inline void ToRight(int step){
				index += step;
				for (int i = 0; i < step; i++)
					node = node->m_next;
			}
		};
		BASSERT(root && !root->IsLeaf());
		while (1)
		{
			NodePos left(root->GetChild(), 0);
			NodePos mid = left;
			NodePos right(root->GetLastChild(), root->m_dist - 1);
			if (!m_flag_stepsearch)
			{
				while (right.index - left.index > m_bsearch_dist)
				{
					mid = left;
					mid.ToRight((right.index - left.index) >> 1);
					if ((*m_comparator)(key, mid.node->GetEntry()->key) >= 0)
						left = mid;
					else
						right = mid;
				}
			}
			else if (right.index - left.index > m_bsearch_dist)
			{
				// 使用二分法，快速缩小子节点区间范围
				int step = 0;
				while (right.index - left.index > m_bsearch_dist)
				{
					// 将区间[left.index,right.index]划分为m_bsearch_dist等分
					// 每等分长度step就是每次前移的步长
					// 判断每个node的第一个Entry的key与给定key的比较关系
					// 给定key>=node的第一个Entry的key
					mid = left;
					step = (right.index - left.index);
					step = (m_bsearch_dist == 4) ? (step >> 2) : (step / m_bsearch_dist);
					for (int i = 0; i < m_bsearch_dist - 1; i++)
					{
						mid = left;
						mid.ToRight(step);
						if ((*m_comparator)(key, mid.node->GetEntry()->key) >= 0)
							left = mid;
						else
						{
							right = mid;
							break;
						}
					}
				}
			}

			// 现在有节点区间[left.index,right.index]，个数少量<=m_bsearch_dist
			// 从左到右遍历，当给定key < 节点的最后一个Entry的key
			// 那么给定key肯定落在此节点中
			mid = left;
			for (int i = left.index; i < right.index; i++, mid.ToRight(1))
			{
				if ((*m_comparator)(key, mid.node->GetLastEntry(m_tail)->key) < 0)
				{
					break;
				}
			}

			// 如果选定节点不是叶子节点，那么进一步在该节点的
			// 子节点中缩小节点范围，递归查找，直到找到叶子节点
			// 节点层级只有固定的4级
			if (mid.node->IsLeaf())
				return FindInsertEntry(key, mid.node, parent);
			root = mid.node;
		}
		return 0;
	}
	SkipNode* SplitFullNode(SkipNode* last)
	{
		// 自动平衡,确保每层的子节点个数在范围[STEP_MIN,STEP_MAX]之间
		// 顶级节点,不裂变
		bool isleaf = true, splited = false;
		int half = 0;			// 前一半的子节点个数
		int count = 0;			// 前一半的所有子节点的Entry个数之和
		if (last->m_dist <= m_step_max)
		{
			CHECK_STATE(last);
			CHECK_STATE(last->m_parent);
		}
		while (last->m_dist > m_step_max && last->m_parent)
		{
			splited = true;
			CHECK_STATE(last->m_parent);

			count = 0;
			half = last->m_dist / 2;
			SkipNode*	first_child = 0;
			Entry*		first_entry = 0;
			if (isleaf)
			{
				count = half;
				first_entry = last->GetEntryByOffset(half);
			}
			else
			{
				SkipNode* sn = last->GetChild();
				for (int i = 0; i < half; i++, sn = sn->m_next)
				{
					BASSERT(sn->m_parent == last);
					count += sn->GetCount();
				}
				first_child = sn;
			}

			// 将此节点裂变成两个加速节点,并将新节点插入到last末尾
			SkipNode* node = NewNode();
			node->m_next = last->m_next;
			node->m_prev = last;
			node->m_parent = last->m_parent;
			node->m_child = first_child;
			node->m_entry = first_entry;
			node->m_dist = last->m_dist - half;
			node->m_count = last->GetCount() - count;

			if (first_entry)
				SetNode(first_entry, node);
			if (first_child)
			{
				SkipNode* sn = first_child;
				for (int i = 0; i < node->m_dist; i++, sn = sn->m_next)
				{
					BASSERT(sn->m_parent == last);
					sn->m_parent = node;
				}
			}

			if (last->m_next)
				last->m_next->m_prev = node;
			last->m_next = node;
			last->m_dist = half;
			last->m_count = count;
			if (last->m_parent)
			{
				BASSERT(last->m_parent->m_dist>0);
				last->m_parent->m_dist++;
			}
			CHECK_STATE(last->m_parent);

			last = last->m_parent;
			isleaf = false;
		}
		BASSERT(last);
		return last;
	}

	SkipNode* RemoveEmptyNode(SkipNode* leaf)
	{
		// 当一个节点的字节点个数为0的时候,需要将其删除
		bool removed = false;
		SkipNode* node = leaf;
		while (node && node->m_dist <= 0)
		{
			removed = true;
			SkipNode* parent = node->m_parent;
			SkipNode* prev = node->m_prev;
			SkipNode* next = node->m_next;
			if (prev)
				prev->m_next = next;
			if (next)
				next->m_prev = prev;

			node->m_parent = 0;
			BASSERT(node->m_entry == 0 && node->m_child == 0);
			if (parent)
			{
				parent->m_dist--;
				if (parent->m_child == node)
				{
					if (parent->m_dist > 0)
					{
						parent->m_child = next;
						BASSERT(next && next->m_parent == parent);
					}
					else
						parent->m_child = 0;
				}
			}
			m_node_count--;
			GetSkipNodePool().Free(node);
			if (node == m_root)
			{
				m_root = 0;
				node = 0;
				BASSERT(m_head == 0 && m_tail == 0 && m_count <= 0);
				break;
			}
			node = parent;
		}
		return removed ? node : leaf;
	}
	void ExpandHashList()
	{
		double ratio = m_hashmap->GetCount()*1.0 / m_hashmap->GetLength();
		if (ratio > m_expand_ratio)
		{
			int length = m_hashmap->GetLength();
			int newlength = m_comparator->GetExpandLength(m_hashmap->GetCount(), length);
			//BVIEW("expand from:%d to %d, ratio:%.4f", length, newlength, newlength*1.0 / length);
			if (newlength <= m_hashmap->GetLength())
				newlength = (int)(m_hashmap->GetLength()*1.5);
			m_hashmap->Expand(newlength);
		}
	}

	void InsertAt(Entry* entry, Entry* newentry)
	{
		BASSERT(entry != newentry && newentry);
		newentry->ver++;
		if (entry)
		{
			if (entry->listprev)
				entry->listprev->listnext = newentry;
			newentry->listprev = entry->listprev;
			newentry->listnext = entry;
			entry->listprev = newentry;
			if (m_head == entry)
				m_head = newentry;
		}
		else// 插到末尾
		{
			if (m_tail)
			{
				BASSERT(m_head);
				newentry->listprev = m_tail;
				newentry->listnext = 0;
				m_tail->listnext = newentry;
				m_tail = newentry;
			}
			else
			{
				// 双链表为空
				BASSERT(m_head == 0);
				m_head = m_tail = newentry;
				m_head->listprev = m_head->listnext = 0;
			}
		}
		if (m_head){
			BASSERT(m_head->listprev == 0);
		}
		if (m_tail){ BASSERT(m_tail->listnext == 0); }
	}
	Entry* RemoveAt(Entry* entry)
	{
		BASSERT(entry);
		Entry* prev = entry->listprev;
		Entry* next = entry->listnext;
		if (next)
			next->listprev = prev;
		if (prev)
			prev->listnext = next;

		if (entry == m_head)
		{
			BASSERT(m_head->GetNode() != 0);
			//m_head->GetNode()->m_entry = next;
			//next->SetNode(m_head->GetNode());
			m_head = next;
		}
		if (entry == m_tail)
			m_tail = prev;

		entry->listprev = entry->listnext = 0;
		m_count--;
		BASSERT(entry != m_head && entry != m_tail);
		if (m_head){ BASSERT(m_head->listprev == 0 && m_head->GetNode()); }
		if (m_tail){ BASSERT(m_tail->listnext == 0); }
		return entry;
	}
	Entry* NewEntry(const Key& key)
	{
		Entry* et = GetEntryPool().Alloc();
		et->key = key;
		et->listprev = et->listnext = 0;
		et->hashprev = et->hashnext = 0;
		et->SetNode(0);
		et->ver = 0;
		//et->changed=et->sortid=0;
		m_count++;
		BASSERT(et != m_head);
		return et;
	}
	SkipNode* NewNode()
	{
		SkipNode* node = GetSkipNodePool().Alloc();
		node->m_next = node->m_prev = 0;
		node->m_parent = node->m_child = 0;
		node->m_entry = 0;
		node->m_dist = node->m_count = 0;
		m_node_count++;
		return node;
	}
	Entry* EraseImp(const Key& key, unsigned int hash = 0, bool remove = false)
	{
		/*
		应用场景:
		设计要求:
		算法复杂度分析:
		*/
		//CHECK_NODES();
		SkipNode* leaf = 0;
		hash = (hash == 0) ? key.GetHash() : hash;
		Entry* entry = FindExist(key, leaf, hash);
		if (!entry)
			return 0;

		BASSERT(leaf && leaf->IsLeaf() && leaf->m_dist > 0);
		if (m_head){ BASSERT(m_head->listprev == 0 && m_head->GetNode()); }
		// 将entry从leaf中删除,并更新计数
		if (leaf->m_entry == entry)
		{
			leaf->m_entry = leaf->m_dist > 1 ? leaf->GetEntryByOffset(1) : 0;
			if (leaf->m_entry)
			{
				if (leaf->m_next){ BASSERT(leaf->m_entry->GetNode() != leaf->m_next); }
				SetNode(leaf->m_entry, leaf);
			}
		}
		if (m_head){ BASSERT(m_head->listprev == 0 && m_head->GetNode()); }
		RemoveAt(entry);
		SetNode(entry, 0);
		BASSERT(entry != m_head && (m_head == 0 || m_head->GetNode()));

		bool del = remove || m_flag_erasehash;
		if (del)
		{
			Entry* et = m_hashmap->Remove(entry->key, hash);
			BASSERT(et == entry);
		}

		//CHECK_NODES();
		if (del)
		{
			BASSERT(entry != m_head && (m_head == 0 || m_head->GetNode()));
			GetEntryPool().Free(entry);
		}

		leaf->m_dist--;
		leaf->AddCountToRoot(-1);
		SkipNode* parent = RemoveEmptyNode(leaf);
		CheckNode("erase",parent ? parent:m_root);
		//CHECK_NODES();
		return del ? 0 : entry;
	}
	void SetNode(Entry* entry, SkipNode* node)
	{
		BASSERT(entry);
		if (node == 0)
		{
			if (m_head == entry)
			{
				BASSERT(0);
			}
		}
		entry->SetNode(node);
	}

	EntryPool& GetEntryPool(){ return m_entry_pool; }
	SkipNodePool& GetSkipNodePool(){ return m_node_pool; }
};
